<?php
/*
 * 跳跃游戏
 * 【题目】
 * 给定数组arr，arr[i]==k代表可以从位置i向右跳1~k个距离。
 * 比如，arr[2]==3，代表从位置2可以跳到位置3、位置4或位置5。
 * 如果从位置0出发，返回最少跳几次能跳到arr最后的位置上。
 * 【举例】
 * arr=[3,2,3,1,1,4]。
 * arr[0]==3，选择跳到位置2；
 * arr[2]==3，可以跳到最后的位置。所以返回2。
 * 【要求】
 * 如果arr长度为N，要求实现时间复杂度为O(N)、额外空间复杂度为O(1)的方法。
 */

$arr = [3,2,3,1,1,4];
$obj = new Code_03_JumpGame();
echo $obj->main($arr);

class Code_03_JumpGame
{
    public function main($arr)
    {
        if (!$arr) {
            return 0;
        }
        $step = 0;
        $curMaxRight = 0;   //step步可到达的最远范围
        $nextMaxRight = 0;  //step+1步可到达的最远范围
        for ($i = 0, $len = count($arr); $i < $len; $i++) {
            if ($curMaxRight < $i) {
                // 目前已经超过了当前最右边界，所以要往前走一步
                $step++;
                $curMaxRight = $nextMaxRight;
            }
            $nextMaxRight = max($nextMaxRight, $i + $arr[$i]);
        }
        return $step;
    }
}